// 案例开放056 [合并区间] 1022上机编程[实验室预约系统设计]学习交流
// http://3ms.huawei.com/km/groups/3803117/blogs/details/11204191
class BookingSystem {
 public:
  struct Node {
    int labId;
    vector<pair<int, int>> times;
    Node(int iLabId) : labId(iLabId) {}
  };
  vector<Node> mAdd;
  map<int, vector<int>> mBook;
  BookingSystem() {}
  int findLad(int labId) {
    for (int i = 0; i < mAdd.size(); ++i) {
      if (mAdd[i].labId == labId) {
        return i;
      }
    }
    return -1;
  }
  bool IsCross(pair<int, int> &p, int startTime, int endTime) {
    return !(p.first >= endTime || p.second <= startTime);
  }
  void merge(vector<pair<int, int>> &times) {
    sort(times.begin(), times.end(),
         [](pair<int, int> &p1, pair<int, int> &p2) {
           return p1.first <= p2.first;
         });
    for (auto iter = times.begin() + 1; iter != times.end();) {
      if (iter->first == (iter - 1)->second) {
        (iter - 1)->second = iter->second;
        times.erase(iter);
      } else {
        iter++;
      }
    }
  }
  bool AddLab(int labId, int startTime, int endTime) {
    int pos = findLad(labId);
    if (pos == -1) {
      Node lab(labId);
      lab.times.emplace_back(startTime, endTime);
      mAdd.push_back(lab);
      return true;
    } else {
      Node &lab = mAdd[pos];
      for (auto &p : lab.times) {
        if (IsCross(p, startTime, endTime)) {
          return false;
        }
      }
      lab.times.emplace_back(startTime, endTime);
      merge(lab.times);
      return true;
    }
  }
  bool InBooking(int labId, int fromTime, int toTime) {
    for (auto p : mBook) {
      if (p.second[0] == labId) {
        pair<int, int> tmp{p.second[1], p.second[2]};
        if (IsCross(tmp, fromTime, toTime)) {
          return true;
        }
      }
    }
    return false;
  }
  int BookTime(int recordId, int fromTime, int toTime) {
    for (auto lab : mAdd) {
      for (auto &p : lab.times) {
        // cout << "lab:" << lab.labId << ' ' << p.first << ' ' << p.second <<
        // endl; cout << "book:" << fromTime << ' ' << toTime << endl;
        if (p.first <= fromTime && p.second >= toTime &&
            !InBooking(lab.labId, fromTime, toTime)) {
          vector<int> book{lab.labId, fromTime, toTime};
          mBook[recordId] = book;
          return lab.labId;
        }
      }
    }
    return -1;
  }
  bool CancelBooking(int recordId) {
    for (auto p : mBook) {
      if (recordId == p.first) {
        mBook.erase(recordId);
        return true;
      }
    }
    return false;
  }
};